//
// Created by 10377 on 2023/12/2.
//

#ifndef PRACTICE1_BINARYTREE_H
#define PRACTICE1_BINARYTREE_H

#include <vector>
#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::to_string;
class TreeNode {

public:
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(): val(0), left(nullptr), right(nullptr) {};
    TreeNode(int val): val(val), left(nullptr), right(nullptr) {};
    TreeNode(int val, TreeNode *left, TreeNode *right): val(val), left(left), right(right) {};
    ~TreeNode(){}
};


class BinaryTree{
private:
    TreeNode *root;
    vector<string> res;

    static vector<int> preorderRecTraversal( TreeNode *root);
    static vector<int> preorderIteTraversal( TreeNode *root);
    static vector<int> inorderRecTraversal( TreeNode *root);
    static vector<int> inorderIteTraversal( TreeNode *root);
    static vector<int> postorderRecTraversal( TreeNode *root);
    static vector<int> postorderIteTraversal( TreeNode *root);
    static vector<vector<int>> levelOrderTraversal(TreeNode* root);
    static void drawTree(TreeNode* root, int depth);
    static TreeNode *CreateTree(vector<int> input, int n);
    static void invertTree(TreeNode *root);
    static  int getHeight(TreeNode* root, int n);
    static bool isBalanced(TreeNode* root);
    vector<string> binaryTreePaths(TreeNode* root);
    void getPath(TreeNode* root, string curPath);
public:
    BinaryTree(): root(nullptr) {}

    void CreateTree(vector<int> input);
    void DeleteTree(TreeNode *root);
    vector<int> preorderRecTraversal();
    vector<int> preorderIteTraversal();
    vector<int> inorderRecTraversal();
    vector<int> inorderIteTraversal();
    vector<int> postorderRecTraversal();
    vector<int> postorderIteTraversal();
    vector<vector<int>> levelOrderTraversal();

    void invertTree();
    void drawTree();
    bool isBalanced();


    vector<string> binaryTreePaths();
    ~BinaryTree(){
        DeleteTree(this->root);
        cout<< "BinaryTree已析构"<<endl;
    }
};

void drawTreePublic(TreeNode* root, int depth);
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder);
TreeNode* constructMaximumBinaryTree(vector<int>& nums);
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2);
#endif //PRACTICE1_BINARYTREE_H
